package day_2023_4_to_7;

/**
 * @author haomin
 * @date 2023/04/19 21:57
 **/
public class Day4_19_Num1043 {
    class Solution {
        public int maxSumAfterPartitioning(int[] arr, int k) {
            int n = arr.length;
            int[][] dp = new int[n+1][k+1];
            for(int i = 1; i <= n; ++i) {
                int v = arr[i-1];
                for(int j = 1; j <= k; ++j) {
                    v = Math.max(v, i-j >= 0 ? arr[i-j] : 0);
                    dp[i][j] = Math.max(dp[i][j-1], (i-j >= 0 ? dp[i-j][k] + v*j : v*i));
                }
            }
            return dp[n][k];
        }
    }
}